package week_six;

import java.util.List;
//f[i][j] i,j节点的最小路径和。
//状态转移： f[i][j] = min(f[i-1][j-1], f[i-1][j]) + triangle[i][j]
// j==0, f[i][j] = f[i-1][0] + triangle[i][j]
// i==j, f[i][j] = f[i-1][j-1] + triangle[i][j]
// 目标 min(f[m-1][j]) , 0=<j<m
public class GetMinPathInTriangleMatrix_120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = m;
        int[][] help = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <= i; j++) {
                if (i == 0 && j == 0) help[i][j] = triangle.get(i).get(j);
                else if (j == 0) help[i][j] = help[i - 1][0] + triangle.get(i).get(j);
                else if (i == j) help[i][j] = help[i - 1][j - 1] + triangle.get(i).get(j);
                else help[i][j] = Math.min(help[i - 1][j - 1], help[i - 1][j]) + triangle.get(i).get(j);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int res : help[m - 1]) {
            min = Math.min(min, res);
        }
        return min;
    }
}
